<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<title>PlanarGC: Tutorial: CutGrid</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript">
  $(document).ready(initResizable);
</script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/search.js"></script>
<script type="text/javascript">
  $(document).ready(function() { searchBox.OnSelectItem(0); });
</script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td style="padding-left: 0.5em;">
   <div id="projectname">PlanarGC
   &#160;<span id="projectnumber">1.0.2</span>
   </div>
  </td>
   <td>        <div id="MSearchBox" class="MSearchBoxInactive">
        <span class="left">
          <img id="MSearchSelect" src="search/mag_sel.png"
               onmouseover="return searchBox.OnSearchSelectShow()"
               onmouseout="return searchBox.OnSearchSelectHide()"
               alt=""/>
          <input type="text" id="MSearchField" value="Search" accesskey="S"
               onfocus="searchBox.OnSearchFieldFocus(true)" 
               onblur="searchBox.OnSearchFieldFocus(false)" 
               onkeyup="searchBox.OnSearchFieldChange(event)"/>
          </span><span class="right">
            <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
          </span>
        </div>
</td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.1.2 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
  <div id="nav-tree">
    <div id="nav-tree-contents">
      <div id="nav-sync" class="sync"></div>
    </div>
  </div>
  <div id="splitbar" style="-moz-user-select:none;" 
       class="ui-resizable-handle">
  </div>
</div>
<script type="text/javascript">
$(document).ready(function(){initNavTree('a00006.html','');});
</script>
<div id="doc-content">
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
<a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark">&#160;</span>All</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark">&#160;</span>Data Structures</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark">&#160;</span>Functions</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark">&#160;</span>Variables</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(4)"><span class="SelectionMark">&#160;</span>Enumerations</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(5)"><span class="SelectionMark">&#160;</span>Enumerator</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(6)"><span class="SelectionMark">&#160;</span>Friends</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(7)"><span class="SelectionMark">&#160;</span>Pages</a></div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<div class="header">
  <div class="headertitle">
<div class="title">Tutorial: <a class="el" href="a00013.html">CutGrid</a> </div>  </div>
</div><!--header-->
<div class="contents">
<div class="textblock"><p><a class="el" href="a00013.html">CutGrid</a> finds a minimal cut in an arbitrary planar grid graph, i.e., in a planar graph such that every node in an mxn grid is a vertex of the graph:</p>
<div class="image">
<img src="introGrid.png" alt="introGrid.png"/>
<div class="caption">
Example of a Grid Graph</div></div>
<p>In order to compute the cut, the following steps have to be performed:</p>
<ol type="1">
<li>Define the <a class="el" href="a00006.html#sec_capGrid">edges' capacity</a> of the graph.</li>
<li>Compute the <a class="el" href="a00006.html#sec_maxflowGrid">maximum flow</a> with respect to a source and a sink.</li>
<li><a class="el" href="a00006.html#sec_getcutGrid">Extract the minimal cut</a> as a vertex-based representation.</li>
</ol>
<p>In the following sections, we explain these steps with respect to the graph sketched in the image above.</p>
<h1><a class="anchor" id="sec_capGrid"></a>
Edges' Capacity</h1>
<p>When we define the capacity of each edge, we can either do this by overwriting <a class="el" href="a00013.html#a55e1ee8a86ead09b026f8cfc9f779afd">CutGrid::edgeCost</a> or by calling <a class="el" href="a00013.html#a132d15a5fd6ef1b9215a0a239a6e1b0c">CutGrid::setEdgeCostFunction</a>. In this simple example we use the latter alternative:</p>
<div class="fragment"><div class="line">CapType edgeCost3x3(<span class="keywordtype">int</span> row, <span class="keywordtype">int</span> col, <a class="code" href="a00013.html#aa6cd9f5a92249e24275933054e182227">CutGrid::EDir</a> dir) {</div>
<div class="line">  <span class="keywordflow">if</span> ((dir == <a class="code" href="a00013.html#aa6cd9f5a92249e24275933054e182227a3d4e2e8cc0c4ec4841d60f72aaed6974">CutGrid::DIR_SOUTH</a>) || (dir == <a class="code" href="a00013.html#aa6cd9f5a92249e24275933054e182227a0bc0dca36823c705e9472b4ecc911933">CutGrid::DIR_NORTH</a>)) <span class="keywordflow">return</span> 3;</div>
<div class="line">  <span class="keywordflow">if</span> ((dir == <a class="code" href="a00013.html#aa6cd9f5a92249e24275933054e182227a7e9ffe4456aaa21d0eb97ea26111f57c">CutGrid::DIR_EAST</a>)  &amp;&amp; (col == 0)) <span class="keywordflow">return</span> 6;</div>
<div class="line">  <span class="keywordflow">if</span> ((dir == <a class="code" href="a00013.html#aa6cd9f5a92249e24275933054e182227ad2ae5884c9205af2a4f30094cdcff70f">CutGrid::DIR_WEST</a>)  &amp;&amp; (col == 1)) <span class="keywordflow">return</span> 6;</div>
<div class="line">  <span class="keywordflow">if</span> (row == 0) <span class="keywordflow">return</span> 10;</div>
<div class="line">  <span class="keywordflow">if</span> (row == 1) <span class="keywordflow">return</span> 9;</div>
<div class="line">  <span class="keywordflow">return</span> 4;</div>
<div class="line">}</div>
</div><!-- fragment --><h1><a class="anchor" id="sec_maxflowGrid"></a>
Maximum Flow</h1>
<p>Now, we have to compute the maximum flow. In order to do this via <a class="el" href="a00013.html">CutGrid</a>, we have to initialize <a class="el" href="a00013.html">CutGrid</a> with the previously defined edge function as well as a source and a sink:</p>
<div class="fragment"><div class="line"><a class="code" href="a00013.html">CutGrid</a> grid_cut(3,3);                        <span class="comment">// defines a 3x3 grid</span></div>
<div class="line"></div>
<div class="line">grid_cut.setEdgeCostFunction(edgeCost3x3);    <span class="comment">// use the previously defined edge cost function</span></div>
<div class="line">grid_cut.setSource(1,0);</div>
<div class="line">grid_cut.setSink(0,2);</div>
</div><!-- fragment --><p>Finally, we have to compute the value of the maximum flow. This is the most time consuming method of the class and is called via</p>
<div class="fragment"><div class="line"><span class="keywordtype">double</span> flow;</div>
<div class="line"></div>
<div class="line">flow = grid_cut.getMaxFlow();</div>
</div><!-- fragment --><h1><a class="anchor" id="sec_getcutGrid"></a>
Extract the Minimal Cut</h1>
<p>For most applications, we are not only interested in the value of the minimum cut, but also in the cut itself. The classical way in describing this cut is to assign a binary labeling to each vertex of the graph. This labeling can be provided via <a class="el" href="a00013.html#a363ca83b7da4990b15fe3c0410617c77">CutGrid::getLabel</a> or <a class="el" href="a00013.html#ade48fa853f0e136a586f8eea360840e2">CutGrid::getLabels</a></p>
<div class="fragment"><div class="line"><a class="code" href="a00014.html#a0e28d67a0303b0b1a43bb9abbad02989">CutPlanar::ELabel</a>  label;</div>
<div class="line"><a class="code" href="a00014.html#a0e28d67a0303b0b1a43bb9abbad02989">CutPlanar::ELabel</a> *labels;</div>
<div class="line"></div>
<div class="line">label  = grid_cut.getLabel(1,2);      <span class="comment">// returns &#39;CutPlanar::LABEL_SOURCE&#39;</span></div>
<div class="line">label  = grid_cut.getLabel(0,0);      <span class="comment">// returns &#39;CutPlanar::LABEL_SINK&#39;</span></div>
<div class="line">labels = <span class="keyword">new</span> <a class="code" href="a00014.html#a0e28d67a0303b0b1a43bb9abbad02989">CutPlanar::ELabel</a>[9];</div>
<div class="line">grid_cut.getLabels(labels);           <span class="comment">// sets {T,T,T,S,S,S,S,S,S}</span></div>
<div class="line">                                      <span class="comment">// with S = CutPlanar::LABEL_SOURCE </span></div>
<div class="line">                                      <span class="comment">//  and T = CutPlanar::LABEL_SINK </span></div>
</div><!-- fragment --><p>The complete code can be seen here: <a class="el" href="a00002.html">cutgrid.cpp</a>. </p>
</div></div><!-- contents -->
</div><!-- doc-content -->
<hr class="footer"/><address style="text-align: right;"><small>
  &copy; 2009 - 2013 by Eno T&ouml;ppe, Frank R. Schmidt
  <br/>
  generated by <a href="http://www.doxygen.org/index.html" target="_blank">Doxygen</a>
</small></address>
